<?php

//比较两份数组的差异，返回差异数组
//相对于new的差异(从new推导old)
//r:lines,lines,...,lines		new中这些行在old中存在
//	lines是line或者start_line-end_line形式，从0开始
//m:lines,lines,...,lines		old中的行
//
//0(r):...,1(m):...,2-?:...		记录无差异部分和差异部分
//输入和输出都是数组
function getChanges($news,$olds) {
	$n_new=count($news);
	$n_old=count($olds);
	for($i=0;$i<$n_new && $i<$n_old && $news[$i]==$olds[$i];$i++);
	$n_perfix=$i;
	$ret=array(0=>'',1=>'');
	if($n_perfix) {
		$ret[0]='0-' . ($n_perfix-1);
		$ret[1]='0-' . ($n_perfix-1);
	}
	if($n_perfix==$n_new || $n_perfix==$n_old) { //纯粹一个在另一个后面添加了点东西
		if($n_perfix!=$n_old) {
			for($i=$n_perfix;$i<$n_old;$i++)
				$ret[$i-$n_perfix+2]=$olds[$i];
		}
		return $ret;
	}
	//不做最大公共子串，只看前缀和后缀的共同部分
	for($i=0;$i<$n_new && $i<$n_old && $news[$n_new-$i-1]==$olds[$n_old-$i-1];$i++);
	$n_suffix=$i;
	if($n_suffix) {
		if($n_perfix) {
			$ret[0].=',' . ($n_new-$n_suffix) . '-' . ($n_new-1);
			$ret[1].=',' . ($n_old-$n_suffix) . '-' . ($n_old-1);
		} else {
			$ret[0]=($n_new-$n_suffix) . '-' . ($n_new-1);
			$ret[1]=($n_old-$n_suffix) . '-' . ($n_old-1);
		}
	}
	for($i=$n_perfix;$i<$n_old-$n_suffix;$i++)
		$ret[$i-$n_perfix+2]=$olds[$i];
	return $ret;
}

function expandNumbers($num) {
	$nums=explode(',',$num);
	$ret=array();
	foreach($nums as $val) {
		if(strpos($val,'-')===false)array_push($ret,(int)$val);
		else {
			$range=explode('-',$val);
			for($i=(int)($range[0]);$i<=(int)($range[1]);$i++)
				array_push($ret,$i);
		}
	}
	return $ret;
}
function recoverChanges($lines,$changes) {
	if(strlen($changes[0])==0)return array_slice($changes,2);
	$ary_in=expandNumbers($changes[0]);
	$ary_out=expandNumbers($changes[1]);
	$ret=array();
	$n_ary=count($ary_in);
	$n_change=count($changes);
	$p_change=2;
	$p_ary=0;
	for($i=0;$p_change<$n_change||$p_ary<$n_ary;$i++) {
		if($p_ary<$n_ary && $ary_out[$p_ary]==$i) {
			$ret[$i]=$lines[$ary_in[$p_ary]];
			$p_ary++;
		} else {
			$ret[$i]=$changes[$p_change];
			$p_change++;
		}
	}
	return $ret;
}

//分隔符\n
function recoverStringChanges($str,$change) {
	return implode("\n",recoverChanges(explode("\n",$str),explode("\n",$change)));
}
function getStringChanges($new,$old) {
	return implode("\n",getChanges(explode("\n",$new),explode("\n",$old)));
}

//need database
function insert_revision($nid,$type,$uid,$comment,$old,$new) {
	$changes = substr(implode("\n",array_slice(getChanges(explode("\n",$old),explode("\n",$new)),2)),0,100);
	$comment = mysql_real_escape_string($comment . ' ' . $changes);
	$change  = mysql_real_escape_string(getStringChanges($new,$old));
	$length  = strlen($new);
	$query='insert into revision (node_id,type,user_id,rev_time,`change`,`length`,comment) values '
		. "($nid,'$type',$uid,now(),'$change',$length,'$comment') ";
	oj_query($query);
}

?>
